//栈
class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2!=0) return false;
        stack<char> st;
        for(char c: s){
            if(c==')'){
                 if(!st.empty()){             
                if(st.top()=='('){
                    st.pop();                  // 匹配成功，消除
                }
                else{
                    st.push(c);                 //未匹配成功，加入st
                }
                }
                else{                              //没有左括号了，不可能匹配
                    return false;
                }
            }
            else if(c=='}'){
                 if(!st.empty()){
                if(st.top()=='{'){
                    st.pop();
                }
                else{
                    st.push(c);
                }
                }
                else{
                    return false;
                }

            }
            else if(c==']'){
                if(!st.empty()){
                if(st.top()=='['){
                    st.pop();
                }
                else{
                    st.push(c);
                }
                }
                else{
                    return false;
                }

            }
            else{
                st.push(c);
            }
            
        }
        
        if(st.empty()){
            return true;
        }
        else{
            return false;
        }

    
    }
};




//利用map优化一下，简化代码



class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2!=0) return false;
        stack<char> st;
        unordered_map <char ,char> mp{{')','('},{'}','{'},{']','['}};
    
        for(char c: s){
            if(mp.count(c)){
                 if(!st.empty()){             
                if(st.top()==mp[c]){
                    st.pop();                  // 匹配成功，消除
                }
                else{
                    st.push(c);                 //未匹配成功，加入st
                }
                }
                else{                              //没有左括号了，不可能匹配
                    return false;
                }
            }
            
            else{
                
                st.push(c);
            }
            
        }
        
        if(st.empty()){
            return true;
        }
        else{
            return false;
        }

    
    }
};

